1.绝对值不等式的本质(1.2.5)
2.德·摩根律在无穷情况下的推广(1.2.12)
3.施罗德-伯恩斯坦双射定理(1.4.13)
4.二维可数集的构造(1.4.8)

实数

习题 1.2 预备知识

(a) 使用反证的方式。假设存在互素整数 $p,q$ 满足 $p/q=\sqrt{3}$，那么 $p^2=3q^2$，$p$ 是 $3$ 的倍数，因此 $q$ 也是 $3$ 的倍数，这与 $p,q$ 互素的假设矛盾。所以 $\sqrt{3}$ 是无理数。

$\sqrt{6}$ 可以用同样的方式证明。

(b) 使用同样的方式，得到 $p^2=4q^2$，但此时只能得到 $p$ 是 $2$ 的倍数，于是可得到 $q=1$，这样不会产生矛盾。

(a) 这是可能不正确的。例如定义

$$A_n=\left\{x\in \mathbb{N}:x\geq n\right\}$$

则有

$$\displaystyle\bigcap_{n=1}^{\infty}{A_n}=\varnothing$$

(b) 这是正确的。证明它的关键是找到一个元素 $x$ 使 $x\in \displaystyle\bigcap_{n=1}^{\infty}{A_n}$。

尝试从有限非空的定义入手。与 (a) 问的区别在于，本题中 $A_{n+1}$ 的元素个数总是不大于 $A_n$ 的元素个数的。所以，从限制元素个数的角度入手，对某一 $k\in \mathbb{Z^+}$，

$$A_k=\left\{x_1,x_2,...,x_p\right\}$$

不妨设 $\exists \ n\in \mathbb{Z^+}$ 使 $\forall\ i\in \left\{1,2,...,p\right\}$ 都有 $x_i\notin A_n$，此时 $A_n\subseteq A_k$， 所以 $A_n=\varnothing$，这与其非空的事实矛盾。所以对 $\forall\ n\in \mathbb{Z^+}$ 都 $\exists \ i\in \left\{1,2,...,p\right\}$ 使得 $x_i\in A_n$，这就证明了 $\displaystyle\bigcap_{n=1}^{\infty}{A_n}$ 的非空性，又有限集合的交集是有限的，故它是有限非空的。

(c) 错误的。事实上左侧表达的是 $x\in A\cap B$ 或 $x\in A\cap C$，右侧表达的是 $x\in A\cap B$ 或 $x\in C$, 左侧是右侧的子集。

(d) 正确的。两者的元素都是同时属于三集合的元素。

(e) 正确的。

(a) 若 $x\in \left(A\cap B\right)^c$，则 $x\notin A$ 或 $x\notin B$，在 $x\in \mathbb{R}$ 的情况下，$x\in A^c$ 或 $x\in B^c$，即 $x\in A^c\cup B^c$，这说明 $\left(A\cap B\right)^c\subseteq A^c\cup B^c$。

(b) 同上反推，这样就能得到 $\left(A\cap B\right)^c= A^c\cup B^c$。

(c) 同理。

(a) 当 $a,b\geq 0$ 时，$|a|=a$，$|b|=b$，因此 $|a+b|\leq|a|+|b|$ 显然成立。

当 $a,b<0$ 时，$|a|=-a$，$|b|=-b$，所以原式可化作 $-(a+b)\leq-(a+b)$，仍然成立。

(b) $a\geq 0$，$b<0$，$a+b\geq 0$ 时，$|a|=a$，$|b|=-b$，$|a+b|=a+b<a-b=|a|+|b|$。

(a) 将 $b$ 替换成 $-b$，因为 $|-b|=|b|$，所以 $|a-b|\leq |a|+|-b|=|a|+|b|$。

(b) 绝对值不等式的本质

这里证明不等式的关键是，$|a+b|\leq|a|+|b|$ 这个不等式左右绝对值内的数字之和是一致的，要证不等式只要满足这个形式，通过赋值就能证明。

要证 $\left||a|-|b|\right|\leq|a-b|$, 其实是证明 $|a|-|b|\leq|a-b|$ 和 $|b|-|a|\leq|a-b|$，它们变形后为 $|a|\leq|a-b|+|b|$ 和 $|b|\leq |b-a|+|a|$，都满足前述绝对值不等式的形式。将绝对值不等式里的 $a$ 替换成 $a-b$ 或者是将 $b$ 替换成 $b-a$，就能证明。

(a) $f(A)=[0,4]$，$f(B)=[1,16]$，$A\cap B=[1,2]$，$A\cup B=[0,4]$，$f(A\cap B)=[1,4]$，$f(A)\cap f(B)=[1,4]$，$f(A\cup B)=[0,16]=f(A)\cup f(B)$。

(b) 由于 $f(x)=x^2$ 在不同的自变量取值下能得到相同的函数值，所以没有交集的集合它们的函数值是可能有交集的。例如取 $A=[-2,-1]$，$B=[1,2]$，$A\cap B=\varnothing$，$f(A\cap B)=\varnothing$，$f(A)\cap f(B)=[1,4]$，$f(A\cap B)\neq f(A)\cap f(B)$。

(c) 由这一映射的定义，对 $x\notin A$，$g(x)\in g(A)$ 的情形， $\exists\ x_1\in A$，$g(x_1)=g(x)$。所以对于这个问题，只需讨论 $A\cup B$ 中的 $x$ 即可。

由定义，$A\cap B$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(A\cap B)$，$A$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(A)$，$B$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(B)$。所以 $g(A\cap B)\subseteq g(A)$ 且 $g(A\cap B)\subseteq g(B)$，从而 $g(A\cap B)\subseteq g(A)\cap g(B)$。

顺带附加说明这个式子在相反方向是不成立的。由 (b) 问的灵感，令 $x_1\in A\setminus B$，$x_2\in B$，若 $g(x_1)=g(x_2)$，由于 $g(x_1)\in g(A)$，$g(x_2)\in g(B)$，此时可得 $g(x_1)\notin g(A\cap B)$ 但是 $g(x_1)\in g(A)\cap g(B)$，所以 $g(A\cap B)\not\subseteq g(A)\cap g(B)$。

(d) $g(A\cup B)=g(A)\cup g(B)$。

同 (c) 问，只需考虑 $A\cup B$ 中的元素即可。令 $x\in A\cup B$，若 $x\in A$，则 $g(x)\in g(A)$，所以 $g(x)\in g(A)\cup g(B)$；若 $x\in B$，同理可得 $g(x)\in g(A)\cup g(B)$。所以 $g(A\cup B)\subseteq g(A)\cup g(B)$。

对于相反方向的情况，若 $g(x)\in g(A)\cup g(B)$，则 $g(x)$ 必定来自于 $g(A)$ 或 $g(B)$，所以 $x$ 必定来自于 $A\cup B$，这就证明了 $g(A)\cup g(B)\subseteq g(A\cup B)$。

所以 $g(A\cup B)=g(A)\cup g(B)$。

(a) $A\cap B=[0,1]$，$A\cup B=[-1,4]$。$f^{-1}(A)=[-2,2]$，$f^{-1}(B)=[-1,1]$，$f^{-1}(A\cap B)=[-1,1]$，$f^{-1}(A\cup B)=[-2,2]$。

所以 $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$，$(1)$

$f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$。$(2)$

(b) 我们要证明对任意的 $g:\mathbb{R}\to \mathbb{R}$, 公式 $(1)$ 和 $(2)$ 仍然成立。

对于 $(1)$,我们有:

$x\in g^{-1}(A\cap B) \iff g(x)\in A\cap B \iff g(x)\in A \text{ 且 } g(x)\in B \iff x\in g^{-1}(A) \text{ 且 } x\in g^{-1}(B) \iff x\in g^{-1}(A)\cap g^{-1}(B)$

所以 $g^{-1}(A\cap B)=g^{-1}(A)\cap g^{-1}(B)$。

同理可得 $g^{-1}(A\cup B)=g^{-1}(A)\cup g^{-1}(B)$。

顺带说明此题和 $1.2.6.$ 结论的区别。事实上这关乎映射的单射性质。$x\mapsto f(x)$ 不一定是一个单射，而 $f(x)\mapsto x$ 一定是一个单射。 事实上，如果是一个单射，那么上述的两个公式将会成立。证明如下：

如果 $f$ 是一个单射，那么对于 $\forall\ x\notin A$，$f(x)\notin f(A)$。 从而 $f(x)\in f(A)\iff x\in A$。所以 $f(x)\in f(A\cap B)\iff x\in A\cap B\iff f(x)\in f(A)\cap f(B)$。$f(x)\in f(A\cup B)\iff x\in A\cup B\iff f(x)\in f(A)\cup f(B)$。

所以有 $f(A\cap B)=f(A)\cap f(B)$，$f(A\cup B)=f(A)\cup f(B)$。

(a) 存在两个实数 $a<b$，对任意 $n\in \mathbb{N}$，$a+1/n\geq b$。

(b) 存在两个实数，它们中间没有有理数。

(c) 存在 $n\in \mathbb{N}$，$\sqrt{n}$ 既不是自然数，也不是无理数。

(d) 存在 $x\in \mathbb{R}$，对 $\forall\ n\in \mathbb{N}$，$n\leq x$。

使用数学归纳法进行证明。假设 $x_n\leq 2$，则 $x_{n+1}=(1/2)x_n+1\leq 2$。

又因为 $x_1=1\leq 2$，所以对任意 $n\in \mathbb{N}$，都有 $x_n\leq 2$。

(a) 同上，假设 $y_n<4$，则 $y_{n+1}=(3y_n+4)/4<4$。又 $y_1=1$，故成立。

(b) 假设 $y_{n+1}>y_n$，则 $y_{n+2}-y_{n+1}=(3y_{n+1}+4)/4-(3y_n+4)/4=3(y_{n+1}-y_n)/4>0$，所以 $y_{n+2}>y_{n+1}$。

又因为 $y_2=7/4>y_1$，所以 $y_n$ 是递增的。

任何一个元素在子集中都有存在/不存在的两种可能性，所以有 $2^n$ 个子集。

(a) 若 $\left(A_1\cup A_2\cup \cdots \cup A_n\right)^c=A_1^c\cap A_2^c\cap \cdots \cap A_n^c$，则有 $\left(A_1\cup A_2\cup \cdots \cup A_n\cup A_{n+1}\right)^c=\left(A_1\cup A_2\cup \cdots \cup A_n\right)^c\cap A_{n+1}^c=A_1^c\cap A_2^c\cap \cdots \cap A_n^c\cap A_{n+1}^c$。又由于 $n=2$ 时是成立的，所以对任意 $n\in \mathbb{Z^+}$ 都成立。

(b) 因为有限是不能直接推广到无限的。

(c) 德·摩根律在无穷情况下的推广

$$\left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c=\displaystyle\bigcap_{n=1}^{\infty}A_n^c$$

是成立的。

设 $x\in (\displaystyle\bigcup_{n=1}^{\infty}A_n)^c$，则对 $\forall\ n\in \mathbb{N}$，$x\notin A_n$，即 $x\in A_n^c$，所以 $x\in \displaystyle\bigcap_{n=1}^{\infty}A_n^c$。这说明 $(\displaystyle\bigcup_{n=1}^{\infty}A_n)^c\subseteq \displaystyle\bigcap_{n=1}^{\infty}A_n^c$。

反之，设 $x\in \displaystyle\bigcap_{n=1}^{\infty}A_n^c$，则对 $\forall\ n\in \mathbb{N}$，$x\in A_n^c$，即 $x\notin A_n$，所以 $x\notin \displaystyle\bigcup_{n=1}^{\infty}A_n$，$x\in (\displaystyle\bigcup_{n=1}^{\infty}A_n)^c$ 。这说明 $\displaystyle\bigcap_{n=1}^{\infty}A_n^c\subseteq \left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c$。

综上所述，$\left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c=\displaystyle\bigcap_{n=1}^{\infty}A_n^c$。

参考资料：MSE上的证明

---

习题 1.3 完备性公理

(a)(b) 显然。

(c) 加法逆元均存在，乘法逆元里 $1,3$为其本身，$2$ 不存在。

$n\in \mathbb{Z^+}$ 时 $\mathbb{Z_n}$ 均存在加法逆元；$n$ 为质数时 $\mathbb{Z_n}$ 均存在乘法逆元。

(a) 称实数 $s$ 是集合 $A\subseteq \mathbb{R}$ 的最大下界， 若满足以下条件：

(i) $s$ 是 $A$ 的下界；

(ii) 若 $b$ 是 $A$ 的任一下界，则 $b\leq s$。

(b) 设 $s$ 是 $A\subseteq \mathbb{R}$ 的一个下界，则 $s=\inf A$ 当且仅当对 $\forall\ \varepsilon>0$，$\exists\ a\in A$，$s+\varepsilon>a$。

(a) 首先，对 $\forall\ a\in A$，$\forall\ b\in B$，有 $b\leq a$，所以集合 $B$ 存在上界，由完备性公理，其存在上确界 $\sup B$。下证 $\sup B=\inf A$。

(i) 若 $a<\sup B$，则 $\exists\ b \in B$，$a<b$，即 $a\notin A$。所以若 $a\in A$，$\sup B\leq a$，这说明 $\sup B$ 是 $A$ 的下界。

(ii) 又对 $\forall\ b\in B$，$b\leq \sup B$，所以 $\sup B$ 是$A$ 的最大下界，由定义，$\sup B=\inf A$。

(b) 完备性公理不需定义最大下界，直接定义下界的上确界即可。

(c) 设集合 $A$ 有下界，即存在 $Q\in \mathbb{R}$ 使得对 $\forall\ a\in A$，$Q\leq a$。要证明它有最大下界，我们从上界入手，试着把它的下界转换成上界。

设 $B=\left\{x\in \mathbb{R}:-x\in A\right\}$，那么对 $\forall\ x\in B$，有 $-x\in A$，所以 $-x\geq Q$，即 $x\leq -Q$，这说明 $B$ 有上界 $-Q$。由完备性公理，$B$ 有上确界 $\sup B$。

(i) 对 $\forall\ x\in B$，$x\leq \sup B$，即 $-x\geq -\sup B$；

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ x\in B$ 使得 $\sup B-\varepsilon<x$，即 $-x<-\sup B+\varepsilon$。

因为 $\forall\ -x\in A$，$\exists\ x\in B$，所以上述两条性质对全体 $a\in A$ 都成立，所以 $A$ 的下确界存在，且 $\inf A=-\sup B$。

由题意，$\sup A$，$\sup B$ 均存在。

因为 $B\subseteq A$，所以对 $\forall\ b\in B$，$b\in A$，即 $b\leq \sup A$，这说明 $\sup A$ 是 $B$ 的一个上界，由 $\sup B$ 的定义，$\sup B\leq \sup A$。

由题意，$\sup A$ 存在。

(a) (i) 对 $\forall\ a\in A$，$a\leq \sup A$。所以对 $\forall\ x\in c+A$，$\exists\ a\in A$，使得 $x=c+a\leq c+\sup A$，所以 $c+\sup A$ 是 $c+A$ 的一个上界。

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ a\in A$ 使得 $\sup A-\varepsilon<a$，所以 $\exists\ x\in c+A$ 使得 $x=c+a>c+\sup A-\varepsilon$。

所以 $\sup (c+A)=c+\sup A$。

(b) $c=0$ 时，$\sup (cA)=0=c\sup A$，显然成立。

$c>0$ 时，(i) 对 $\forall\ x\in cA$，$\exists\ a\in A$，使得 $x=ca\leq c\sup A$，所以 $c\sup A$ 是 $cA$ 的一个上界。

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ a\in A$ 使得 $\sup A-\varepsilon<a$，所以 $\exists\ x\in cA$ 使得 $x=ca>c\sup A-c\varepsilon$,由 $\varepsilon$ 的任意性，得证。

所以 $\sup (cA)=c\sup A$。

(c) $c<0$ 时，$\sup (cA)=c\inf A$。通过改变不等号方向即可证明。

(a) 上确界 $3$，下确界 $1$。

(b) $1$，$0$。

(c) $1/2$，$1/3$。

(d) $9$，$1/9$。

对任何一个上界 $b$，因为 $a\in A$，所以 $a\leq b$，这说明 $a=\sup A$。

取 $\varepsilon=(\sup B-\sup A)/2$，则 $\exists\ b\in B$，$b>\sup B-\varepsilon=(\sup B+\sup A)/2>\sup A$，所以 $b$ 是 $A$ 的一个上界。

(a) 真。

(b) 假。考虑 $A=\left\{x\in \mathbb{Q}: x^2<2\right\}$，其内的任意元素都小于 $\sqrt{2}$，但是 $\sup A=\sqrt{2}$。

(c) 假。 考虑 (b) 中的 $A$ 和 $B=\left\{x\in \mathbb{Q}: x^2>2,x>0\right\}$，则对 $\forall\ a\in A,b\in B$ 有 $a<b$，但是 $\sup A=\inf B=\sqrt{2}$。

(d) 真。

(e) 假。考虑 (b) 中的 $A$，令 $B=A$，则 $\sup B=\sup A$，此时不存在 $b\in B$，使得 $b\geq \sup A$。

---

习题 1.4 完备性的推论

$a<0<b$ 时，$0$ 即为答案。

$a<b\leq 0$ 时，化成 $0\leq -b<-a$ 即可转化为前述情况证明。

(a) 由于 $a,b\in \mathbb{Q}$，那么可令 $a=p_1/q_1$，$b=p_2/q_2$，那么 $a+b=(p_1q_2+p_2q_1)/q_1q_2\in \mathbb{Q}$，同理 $ab\in \mathbb{Q}$。

(b) 由 $(a)$，若 $a+t\in \mathbb{Q}$，则 $t=(a+t)-a\in \mathbb{Q}$，所以 $a+t\in \mathbb{R}\backslash\mathbb{Q}$，同理 $at\in \mathbb{R}\backslash\mathbb{Q}$。

(c) $\mathbb{R}\backslash \mathbb{Q}$ 在加法和乘法下不封闭，更精确地说，无理数的运算结果可能是有理数。

任意两个实数 $a,b$ 之中必有一个有理数 $q$，使得 $a<q<b$。

所以 $a-\sqrt{2}<q-\sqrt{2}<b-\sqrt{2}$，由 $1.4.2.$ 可知 $q-\sqrt{2}$ 是无理数。

首先，对于 $\forall\ n\in \mathbb{Z^+}$，有 $0<1/n$，所以 $0$ 是 $\{1/n:n\in \mathbb{Z^+}\}$ 的一个下界。

下面证明 $0$ 是下确界。事实上由实数的阿基米德性，对 $\forall\ y>0$，$\exists\ n\in \mathbb{Z^+}$，$1/n<y$，所以任何比 $0$ 大的数都不是下界，即 $0$ 是下确界。

由阿基米德性的结论即可知对 $\forall\ y>0$，$y\notin \displaystyle\bigcap_{n=1}^{\infty} (0,1/n)$。所以 $\displaystyle\bigcap_{n=1}^{\infty} (0,1/n)=\varnothing$。

(a) 若 $\alpha^2>2$，对 $n\in \mathbb{N}^+$，取 $(\alpha-1/n)^2=\alpha^2-2\alpha/n+1/n^2>\alpha^2-2\alpha/n>2$，得 $n>2\alpha/(\alpha^2-2)$，所以 $\alpha-1/n$ 也是 $T$ 的上界，矛盾。

这里默认了 $\alpha>0$。

(b) $b=0$ 时是显然成立的。

$b>0$ 时，考虑集合 $T=\{t>0:t^2<b\}$。$b<1$ 时，$b\in T$ 且 $1$ 是 $T$ 的上界，所以 $\sup T$ 存在。$b\geq 1$ 同理可得其存在性。

令 $x=\sup T$，下面证明 $x^2=b$。

(i) 若 $x^2<b$，对 $n\in \mathbb{N}^+$，取 $(x+1/n)^2=x^2+2x/n+1/n^2<x^2+(2x+1)/n<b$，得 $n>(2x+1)/(b-x^2)$，即 $x+1/n$ 可能属于 $T$，矛盾。

(ii) 若 $x^2>b$，对 $n\in \mathbb{N}^+$，取 $(x-1/n)^2=x^2-2x/n+1/n^2>x^2-2x/n>b$，得 $n>2x/(x^2-b)$，即 $x-1/n$ 是 $T$ 的上界，矛盾。

所以 $x^2=b$。即 $x=\sqrt{b}$。

设 $n_2=\min \{n\in \mathbb{N}^+:f(n)\in A,n>n_1\}$，令 $g(2)=f(n_2)$。

以此类推，对于 $g(k)=f(n_k)$，由于 $A$ 是无限集，所以总存在 $n_{k+1}=\min \{n\in \mathbb{N}^+:f(n)\in A,n>n_k\}$，令 $g(k+1)=f(n_{k+1})$。

这样就得到了 $g:\mathbb{N}^+\to A$ 的映射。

(a) 如果 $B_2$ 是无限集，那么由 $1.4.7.$ 可知，$B_2$ 是可数集，那么存在两个双射 $f,g$，有 $f:\mathbb{N}^+\to A_1$，$g:\mathbb{N}^+\to B_2$。现在定义映射 $h:\mathbb{N}^+\to A_1\cup B_2$ 为

$$h(n)=\begin{cases} f\left(\frac{n+1}{2}\right), & n \text{ 为奇数}\\ g\left(\frac{n}{2}\right), & n \text{ 为偶数且不为0}\\ \end{cases}$$

由 $A_1\cap B_2=\varnothing$，可知 $h$ 是单射。由 $f,g$ 的双射性知 $h$ 是满射，于是 $h$ 是双射。这说明 $A_1\cup B_2$ 即 $A_1\cup A_2$ 是可数集。

如果 $B_2$ 是有限集，设它其中的元素个数为 $m$，则 $B_2=\{b_1,b_2,\ldots,b_m\}$。存在双射 $f:\mathbb{N}^+\to A_1$。现在定义映射 $h:\mathbb{N}^+\to A_1\cup B_2$ 为

$$h(n)=\begin{cases} b_n, & n\leq m\\ f(n-m), & n>m\\ \end{cases}$$

同上可得 $h$ 是双射。所以 $A_1\cup B_2$ 即 $A_1\cup A_2$ 是可数集。

(b) 使用数学归纳法。假设 $A_1,A_2,\ldots,A_n$ 是可数集时 $A_1\cup A_2\cup\ldots\cup A_n$ 是可数集，令 $B=A_1\cup A_2\cup\ldots\cup A_n$，则 $A_{n+1}$ 是可数集时 $B\cup A_{n+1}$ 即 $A_1\cup A_2\cup\ldots\cup A_n\cup A_{n+1}$ 也是可数集。又 $n=2$ 时结论成立，由数学归纳法可知结论对 $\forall\ n\in \mathbb{N}^+$ 成立。

由 $1.2.12.(b)$ 可知，有限归纳法不能直接推广到无限的情况。

(c) 二维正整数集为可数集的对角线构造证明法

由图所示，我们可以构造映射 $f:\mathbb{(N^+)^2}\to \mathbb{N^{+}}$，

$$f(m,n)=\begin{cases} 1, &\text{if } m=n=1;\\ f(m+1,n-1)+1, &\text{if } n>1;\\ f(1,m-1)+1, &\text{if } m>1,n=1; \end{cases}$$

$(m,n)$ 是下面这个数表下面第 $m$，右边第 $n$ 个元素：

$$\begin{array}{ccccc} & 1 & 3 & 6 & 10 &\cdots\\ & 2 & 5 & 9 & 14 &\cdots\\ & 4 & 8 & 13 & 19 &\cdots\\ & 7 & 12 & 18 & 25 &\cdots\\ & \vdots & \vdots & \vdots & \vdots \end{array}$$

可以看出，全体正整数都出现在这个表中，且每个正整数只出现一次。所以 $f$ 是一个双射。下面我们严格地证明这一点。

首先，我们证明 $f$ 是单射。 当横纵坐标之和固定时，这些点都在同一对角线上，我们利用这个性质给出下面的证明：

设 $f(m_1,n_1)=f(m_2,n_2)$， 不失一般性，令 $m_1+n_1\leq m_2+n_2$，此时 $(m_1,n_1)$ 所在的对角线在 $(m_2,n_2)$ 所在的对角线的上方（也是左侧）或与之重合。

若不重合即 $m_1+n_1<m_2+n_2$，则 $f(m_1,n_1)\leq f(1,m_1+n_1-1)<f(m_1+n_1,1)$，移动到下一条对角线上，直到 $(m_2,n_2)$ 所在的对角线，即移到 $f(m_1+n_1+k,1)$，其中 $m_1+n_1+k+1=m_2+n_2$。由一条对角线上的单调性，由 $n_2\geq 1$，有 $f(m_2,n_2)\geq f(m_1+n_1+k,1)>f(m_1,n_1)$。这就矛盾。

所以 $m_1+n_1=m_2+n_2$，即 $(m_1,n_1)$ 和 $(m_2,n_2)$ 在同一条对角线上。由对角线上的单调性，$m_1\geq m_2$ 可推出 $f(m_1,n_1)\leq f(m_2,n_2)$，所以 $m_1=m_2$，进而 $n_1=n_2$。综上所述，$f$ 是单射。

接着证明 $f$ 是满射，使用数学归纳法。假设对某个 $k\in \mathbb{N^+}$，$\exists\ m,n\in \mathbb{N^+}$，使得 $f(m,n)=k$，则对 $k+1$，有

$$\begin{matrix} f(m-1,n+1)=f(m,n)+1=k+1, &\text{if } m>1;\\ f(n+1,m)=f(m,n)+1=k+1, &\text{if } m=1; \end{matrix}$$

而 $f(1,1)=1$，所以 $f$ 是满射。

综上所述，$f$ 是双射。

对无穷多个可数集 $A_1,A_2,\ldots$，令 $B_1=A_1$，$B_2=A_2\backslash A_1$，$B_3=A_3\backslash (A_1\cup A_2)$，依此类推，$B_n=A_n\backslash (A_1\cup A_2\cup\ldots\cup A_{n-1})$，则 $A_1,A_2,\ldots$ 的并集可表示为 $B_1\cup B_2\cup B_3\cup\ldots$，且 $B_i\cap B_j=\varnothing$（$i\neq j$）。

若对 $\forall\ i\in \mathbb{N}^+$，$B_i$ 是可数集，设 $B_i=\{b_{i1},b_{i2},\ldots\}$，则定义映射 $g:\mathbb{N}^+\to B_1\cup B_2\cup B_3\cup\ldots$ 为 $f(m,n)\mapsto b_{mn}$，由定义可知 $g$ 是双射，所以 $A_1\cup A_2\cup A_3\cup\ldots$ 是可数集。

若 $\exists\ i\in \mathbb{N}^+$，$B_i$ 是有限集，令 $C$ 为这些有限集的并集，仿照 $1.4.8.(a)$ 中的构造方法，可知 $C$ 是可数集，于是也能得证。

综上， $A_1\cup A_2\cup A_3\cup\ldots$ 是可数集。

(a) 由题意，存在双射 $f:A \to B$。则构造 $g:B \to A$ 使得 $g(f(x)) = x$ 对任意 $x \in A$ 成立。由于 $f$ 是双射，$g$ 也是双射。所以 $B \sim A$。

(b) 由题意，存在双射 $f:A \to B$ 和双射 $g:B \to C$。则构造 $h:A \to C$ 使得 $h(x) = g(f(x))$ 对任意 $x \in A$ 成立。由于 $f,g$ 是双射，$h$ 也是双射。所以 $A \sim C$。

将子集按元素和从小到大，元素个数从少到多排列：$\{1\},\{2\},\{3\},\{1,2\},\ldots$，则每个子集都能对应一个唯一的自然数。故所有有限子集的集合可数。

(a) $f:x\mapsto (x,1/2)$。

(b) 构造如下的映射 $g:S\to (0,1)$：令 $x=0.a_1a_2\ldots$，$y=0.b_1b_2\ldots$，则 $g(x,y)=k$，其中 $k=0.a_1b_1a_2b_2\ldots$。

由于每个实数都有唯一的无限小数表示，由此知 $g$ 为满射。

(a) $(\sqrt{2})^2-2=0$，$(\sqrt[3]{2})^3-2=0$。

令 $t=\sqrt{2}+\sqrt{3}$，考虑 $t^2=5+2\sqrt{6}$，则 $(t^2-5)^2-24=0$，展开来得 $t^4-10t^2+1=0$。

所以它们都是代数数。

(b) 令 $B_m$ 为系数满足 $m-1<\displaystyle \sum_{i=0}^{n}|a_i|\leq m$ 的多项式的根的集合。显然满足 $B_m$ 条件的多项式个数有限，每个多项式的根的个数也有限，所以 $B_m$ 是有限集。

所以 $A_n=\displaystyle\bigcup_{m=1}^\infty B_m$ 由 $1.4.8.$ 知是可数集。

(c) 所有代数数的集合为 $\displaystyle\bigcup_{n=1}^\infty A_n$，由 $1.4.8.$ 知是可数集。

超越数集合是不可数的，换句话说，超越数的个数比代数数要多得多。

(a) 因为 $f$ 是单射，所以若 $f(x_1) = f(x_2)=y$，则有 $x_1 = x_2$，这就说明 $f(x)=y$ 的唯一性，因此 $f^{-1}$ 是良定义且单射的。

(b) 如果不存在 $y\in Y$ 使得 $g(y)=x$，那么 $g^{-1}(x)$ 不存在，因此左侧元素数量为 $0$。

同理，如果左侧延伸到某个元素满足上述情况，那么链在该元素截断，左侧元素数量有限。

若对左侧任何一个元素 $x$，$x\in Y$ 时 $f^{-1}(x)$ 存在， $x\in X$ 时 $g^{-1}(x)$ 存在，那么链可以无限延伸下去，左侧元素数量无限。

(c) 如果两条链所有元素都不相同就不相交。

如果两条链有一个元素相同，由 $f,g$ 的单射性可知，该元素左侧和右侧的所有元素都相同，因此两条链完全相同。

(d) 考虑链 $C_x$ 中的一个元素 $y\in Y$。

若 $y\in f(X)$，则链延伸到 $f^{-1}(y)$，否则链在 $y$ 截断，$C_x\subseteq B$。

若链在 $f^{-1}(y)$ 截断，那么对链中任意的 $x\in Y$ 都有 $x\in f(X)$，$C_x\subseteq A$。

如果继续往左延伸到某个元素 $x$ 使得 $f^{-1}(x)$ 不存在，那么 $C_x\subseteq B$。

如果一直无限延伸，$C_x\subseteq A$。

所以所有 $C_x\subseteq B$ 都以 $y\notin f(X)$ 为头开始。

(e) 根据 (c) 可知，所有链 $C_x$ 互不相交，于是 $f$ 将 $X_1$ 映到 $Y_1$，$g$ 将 $Y_2$ 映到 $X_2$。

又由题意，$X_1\cup X_2=X$，$Y_1\cup Y_2=Y$，根据 $f:X_1\to Y_1$ 和 $g:Y_2\to X_2$ 的双射性，构造如下的映射 $h:X\to Y$：

$$h=\begin{cases} f(x), & x\in X_1,\\ g^{-1}(x), & x\in X_2. \end{cases}$$

显然 $h$ 是双射。所以 $X\sim Y$。

---

习题 1.5 Cantor 定理

$\Rightarrow)$ 若 $(0,1)$ 不可数，由于可数集的子集可数，所以 $\mathbb{R}$ 也不可数。

$\Leftarrow)$ 若 $\mathbb{R}$ 不可数，假设 $(0,1)$ 可数，则 $[0,1)$ 同样可数，由于 $f:[0,1)\to [1,2)$，$f(x)=x+1$ 是一个双射，所以 $[1,2)$ 可数，同样对 $\forall\ x\in \mathbb{Z}$，$[x,x+1)$ 可数，所以 $\mathbb{R}=\displaystyle \bigcup_{x\in \mathbb{Z}}[x,x+1)$ 可数，矛盾。

故 $(0,1)$ 不可数。

(b) 对 $\forall\ x\in \mathbb{N}$，$b_n\neq a_{nn}$，所以 $x\neq f(n)$。

(c) 由 (b) 可知这样的列表无法覆盖整个 $(0,1)$，所以 $(0,1)$ 不可数。

(a) 表中的小数都是实数，各位数都可以随意列出。如果换成有理数：(1) 表中的小数无法任意排布；(2) 得到的表格外面的数不一定是有理数。因此无法用对角线法证明有理数不可数。

(b) 将所有有限小数都写成它的无限小数形式即可规避该问题。

假设 $S$ 可数，则可以使用对角线法构造一个如下的表格：

$$\begin{matrix} &1\longleftrightarrow (a_{11},a_{12},a_{13},\ldots)\\ &2\longleftrightarrow (a_{21},a_{22},a_{23},\ldots)\\ &3\longleftrightarrow (a_{31},a_{32},a_{33},\ldots)\\ &\vdots\\ &d\longleftrightarrow (a_{d1},a_{d2},a_{d3},\ldots)\\ &\vdots \end{matrix}$$

然后构造一个新的序列 $(b_1,b_2,b_3,\ldots)$，其中 $b_i\neq a_{ii}$，则该序列不在表格中，矛盾。

故 $S$ 不可数。

(a) $\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$。

(b) 对于 $A$ 的任意子集，都可以用一个 $0-1$ 序列来表示，$1$ 表示该位置的元素在子集中，$0$ 表示不在。因此列出后可得到 $2^n$ 个子集。

(a) $A\to P(A)$：(1) $a\mapsto \{a\}$，(2) $a\mapsto \varnothing$。

(b) $B\to P(B)$：$b\mapsto \{b\}$。

因为 P(A) 中的元素个数远大于 A 中的元素个数，所以不可能有一个满射。

采用 $A\to P(A)$：(1) $a\mapsto \{a\}$ 的规则，得到 $B=\varnothing$。

(a) 若 $a'\in B$，则 $a'\notin f(a')$，但 $B=f(a')$，矛盾。

(b) 若 $a'\notin B$，则 $a'\in f(a')$，但 $B=f(a')$，矛盾。

所以从 $A$ 到 $P(A)$ 不存在一个满射函数。

(a) 建立 $f:\{0,1\}\to \mathbb{N^+}$: $f(0)=a,f(1)=b$，把所有这样的函数组成集合 $A$ 。我们再建立 $g:A\to \mathbb{(N^+)^2}$: $g(f)=(a,b)$。显然，$g$ 是一个双射。由前述构造，$\mathbb{N}\sim \mathbb{(N^+)^2}$，所以集合 $A$ 可数。

(b) 同上，建立 $f:\mathbb{N^+}\to \{0,1\}$，这个 $f$ 把正整数序列转换成了无穷的 $0-1$ 序列，由 $1.5.4.$ 可知这样的序列不可数，所以全体 $f$ 组成的集合不可数。

(c) 这里借鉴了别人的解答。

设 $p_m$ 是第 $m$ 个素数。我们利用素数的唯一分解性来构造一个映射：

$$\Phi:P(\mathbb{N^+})\setminus\left\{\varnothing,\mathbb{N^+}\right\} \to P(\mathbb{N^+}):\\ \Phi\left(X\right)=\left\{p_m^n: m\in X,n\notin X\right\}$$

记 $\mathcal{A}=\left\{\Phi(X): X\in P(\mathbb{N}^+)\setminus\left\{\varnothing,\mathbb{N^+}\right\}\right\}$，下面我们要证明 $\mathcal{A}$ 是一个不可数的反链，即对任意 $X\neq Y$，都有 $\Phi(X)\not\subseteq \Phi(Y)$ 且 $\Phi(Y)\not\subseteq \Phi(X)$。

首先，由素数的唯一分解性，$\Phi$ 是一个单射。

不妨设 $\exists\ m\in X$，$m\notin Y$（即 $X \not\subseteq Y$），则对某个 $n\notin X$，$p_m^n\in \Phi(X)$，但 $p_m^n\notin \Phi(Y)$（因为底数 $m \notin Y$），所以 $\Phi(X)\not\subseteq \Phi(Y)$。

对于反方向 $\Phi(Y) \not\subseteq \Phi(X)$：
如果 $\exists\ l\in Y$，$l\notin X$（即 $Y \not\subseteq X$），则同理可证 $\Phi(Y)\not\subseteq \Phi(X)$。
如果对 $\forall\ l\in Y$，$l\in X$（即 $Y \subsetneq X$），则对上述 $m$（满足 $m \in X \setminus Y$），任取 $l \in Y$，考察元素 $z = p_l^m$。
$z \in \Phi(Y)$（因底数 $l \in Y$，指数 $m \notin Y$）。
但 $z \notin \Phi(X)$（因指数 $m \in X$，不满足 $\Phi(X)$ 的定义要求）。
所以 $\Phi(Y)\not\subseteq \Phi(X)$。

综上，$\mathcal{A}$ 中任何元素都不是其他元素的子集。又因为 $P(\mathbb{N^+})\setminus\left\{\varnothing,\mathbb{N^+}\right\}$ 是不可数的，所以 $\mathcal{A}$ 也是不可数的。

所以，$\mathcal{A}$ 就是一个不可数的反链。

---